/*
    贪心经典题目专题3
    
    前置知识: 
    讲解005、042 - 对数器
    讲解025、026、027 - 基础排序、有序表、比较器、堆结构

    狭义的贪心
    每一步都做出在当前状态下最好或最优的选择，从而希望最终的结果是最好或最优的算法

    广义的贪心
    通过分析题目自身的特点和性质，只要发现让求解答案的过程得到加速的结论，都算广义的贪心

    贪心是最符合自然智慧的思想，一般分析门槛不高
    理解基本的排序、有序结构，有基本的逻辑思维就能理解
    但是贪心的题目，千题千面，极难把握
    难度在于证明局部最优可以得到全局最优，好在！我们有对数器！贪心专题2、3，这两节大量使用对数器

    ================================================

    有关贪心的若干现实 & 提醒
    1，不要去纠结严格证明，每个题都去追求严格证明，浪费时间、收益很低，而且千题千面。玄学！
    2，一定要掌握用对数器验证的技巧，这是解决贪心问题的关键
    3，解法几乎只包含贪心思路的题目，代码量都不大
    4，大量累积贪心的经验，重点不是证明，而是题目的特征，以及贪心方式的特征，做好总结方便借鉴
    5，关注题目数据量，题目的解可能来自贪心，也很可能不是，如果数据量允许，能不用贪心就不用（稳）
    6，贪心在笔试中出现概率不低，但是面试中出现概率较低，原因是 淘汰率 vs 区分度
    7，广义的贪心无所不在，可能和别的思路结合，一般都可以通过自然智慧想明白，依然不纠结证明

    ================================================

    题目1
    最短无序连续子数组
    给你一个整数数组nums，你需要找出一个 连续子数组
    如果对这个子数组进行升序排序，那么整个数组都会变为升序排序
    请你找出符合题意的最短子数组，并输出它的长度
    测试链接 : https://leetcode.cn/problems/shortest-unsorted-continuous-subarray/

    ================================================

    题目2
    最小区间
    你有k个非递减排列的整数列表
    找到一个最小区间，使得k个列表中的每个列表至少有一个数包含在其中
    测试链接 : 
    https://leetcode.cn/problems/smallest-range-covering-elements-from-k-lists/

    本题需要理解有序表，讲解026，有序表的用法
    虽然不用有序表也能做，但是有序表的方法最好理解

    ================================================

    题目3
    组团买票
    景区里一共有m个项目，景区的第i个项目有如下两个参数：
    game[i] = { Ki, Bi }，Ki、Bi一定是正数
    Ki代表折扣系数，Bi代表票价，举个例子 : Ki = 2, Bi = 10
    如果只有1个人买票，单张门票的价格为 : Bi - Ki * 1 = 8
    所以这1个人游玩该项目要花8元
    如果有2个人买票，单张门票的价格为 : Bi - Ki * 2 = 6
    所以这2个人游玩该项目要花6 * 2 = 12元
    如果有5个人买票，单张门票的价格为 : Bi - Ki * 5 = 0
    所以这5个人游玩该项目要花5 * 0 = 0元
    如果有更多人买票，都认为花0元(因为让项目倒贴钱实在是太操蛋了)
    于是可以认为，如果有x个人买票，单张门票的价格为 : Bi - Ki * x
    x个人游玩这个项目的总花费是 : max { x * (Bi - Ki * x), 0 }
    单位一共有n个人，每个人最多可以选1个项目来游玩，也可以不选任何项目，由你去按照上面的规则，统一花钱购票
    你想知道自己需要准备多少钱，就可以应付所有可能的情况，返回这个最保险的钱数
    1 <= M、N、Ki、Bi <= 10^5
    来自真实大厂笔试，没有在线测试，对数器验证

    ================================================

    题目4
    平均值最小累加和
    给定一个数组arr，长度为n
    再给定一个数字k，表示一定要将arr划分成k个集合
    每个数字只能进一个集合
    返回每个集合的平均值都累加起来的最小值
    平均值向下取整
    1 <= n <= 10^5
    0 <= arr[i] <= 10^5
    1 <= k <= n
    来自真实大厂笔试，没有在线测试，对数器验证

    ================================================

    题目5
    执行所有任务的最少初始电量
    每一个任务有两个参数，需要耗费的电量、至少多少电量才能开始这个任务
    返回手机至少需要多少的初始电量，才能执行完所有的任务
    来自真实大厂笔试，没有在线测试，对数器验证

    ================================================

    题目6
    两个0和1数量相等区间的最大长度
    给出一个长度为n的01串，现在请你找到两个区间
    使得这两个区间中，1的个数相等，0的个数也相等
    这两个区间可以相交，但是不可以完全重叠，即两个区间的左右端点不可以完全一样
    现在请你找到两个最长的区间，满足以上要求
    返回区间最大长度
    来自真实大厂笔试，没有在线测试，对数器验证

*/